package com.xypower.sort;

import java.util.PriorityQueue;
//堆排序
public class heapTest {

    public static void main(String[] args) {
        //小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        heap.add(8);
        heap.add(4);
        heap.add(4);
        heap.add(9);
        heap.add(10);
        heap.add(3);
        while (!heap.isEmpty()){
            System.out.println(heap.poll());
        }
    }
    //队列排序
    public void sortedArrDistanceLessK(int[] arr,int k){
        //默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        int index = 0;
        for (;index<=Math.min(arr.length,k);index++){
            heap.add(arr[index]);
        }
        int i = 0;
        for (;index < arr.length;i++,index++){
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        while (!heap.isEmpty()){
            arr[i++]=heap.poll();
        }
    }

    //堆排序
    public static void heapSort(int[] arr){
        if (arr==null || arr.length<2){
            return;
        }
        for (int i=0;i<arr.length;i++){//o(N)
            heapInsert(arr,i);  //o(logN)
        }

//        for (int i =arr.length-1;i>=0;i--){
//            heapify(arr,i,arr.length);
//        }

        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize>0){//o(N)
            heapify(arr,0,heapSize);//o(logN)
            swap(arr,0,--heapSize);//o(1)
        }
    }

    //通过heapinsert方法解决不是大根堆问题,向上移动 时间复杂度logN
    public static void heapInsert(int[] arr,int index){
        while (arr[index] > arr[(index-1)/2]){//当前数大于父位置的数
            swap(arr,index,(index-1)/2);    //交换
            index = (index-1)/2;               //到父位置继续循环进行判断
        }
    }

    //求最大值并去掉
    //某个数在index位置，是否向下移动  时间复杂度logN
    public static void heapify(int[] arr,int index,int heapSize){
        int left = index*2+1;//左孩子的下标
        while (left<heapSize){//左孩子不越界，一定有孩子
            //两个孩子中谁的值大，把下标给largest
            int largest = left + 1 < heapSize && arr[left +1] > arr[left]
                    ? left+1 : left;
            //父和孩子之间，谁的值大，把下标给largest
            largest = arr[largest] > arr[index]  ? largest : index;
            if (largest == index){
                break;
            }
            swap(arr,largest,index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
